/*
 * @Description:
 * @Version: 2.0
 * @Autor: zhuyijun
 * @Date: 2021-03-31 10:57:16
 * @LastEditors: zhuyijun
 * @LastEditTime: 2021-03-31 11:07:30
 */

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}
/**
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000
 */
//方法1 回溯
func reversePrint(head *ListNode) []int {
	res := make([]int,0)
	var reverse func(*ListNode)
	reverse = func(node *ListNode) {
		if node.Next != nil {
			reverse(node.Next)
		}
		res = append(res, node.Val)
	}
	if head == nil {
		return nil
	}
	reverse(head)
	return res
}
/**
方法二 一般递归
 */
func reversePrint2(head *ListNode) []int {
	if head == nil {
		return nil
	}
	var nums []int
	nums = readList(head,nums)
	len :=len(nums)
	for  i:= 0; i < len >> 1; i++{
		temp := nums[i];
		nums[i] = nums[len - i - 1];
		nums[len - i - 1] = temp;
	}
	return nums
}

func readList(head *ListNode,nums []int)[]int  {
	nums = append(nums, head.Val)
	print(head.Val)
	if head.Next == nil {
		return nums
	}
	return  readList(head.Next,nums)
}

/**
递归回溯
 */
func reversePrint3(head *ListNode) []int {
	if head == nil {
		return nil
	}
	var nums []int
	readList3(head,&nums)
	return nums
}

func readList3(head *ListNode,nums* []int) {
	if head.Next != nil {
		readList3(head.Next,nums)
	}
	*nums = append(*nums, head.Val)
}


func main() {
	l := &ListNode{2, &ListNode{1, &ListNode{3, nil}}}
	fmt.Printf("%v",reversePrint3(l))
}
